home *** CD-ROM | disk | FTP | other *** search
/ 3D GFX / 3D GFX.iso / amiutils / i_l / irit5 / illustrt / intersct.c < prev    next >
C/C++ Source or Header  |  1995-12-30  |  22KB  |  598 lines
  1. /*****************************************************************************
  2. * Computes all intersection points in given set of polylines.             *
  3. *                                         *
  4. * Written by:  Gershon Elber                Ver 1.0, June 1993   *
  5. *****************************************************************************/
  6.  
  7. #include <stdio.h>
  8. #include <math.h>
  9. #include "program.h"
  10. #include "imalloc.h"
  11. #include "ln_sweep.h"
  12.  
  13. /* #define DEBUG_DUMP_POLYS */
  14. /* #define DEBUG_DUMP_INTERS */
  15.  
  16. #define DIST_PT_PT_2D(Pt1, Pt2) sqrt(SQR(Pt1[0] - Pt2[0]) + \
  17.                      SQR(Pt1[1] - Pt2[1]))
  18.  
  19. typedef struct PolylineSegStruct {
  20.     struct PolylineSegStruct *Pnext;
  21.     LsIntersectStruct *Inter;
  22.     IPPolygonStruct *Poly;
  23.     int Index;                 /* i'th linear segment in polyline. */
  24.     RealType t;          /* Parameter value between 0 to 1 of intersection. */
  25. } PolylineSegStruct;
  26.  
  27. static IPPolygonStruct *SplitPolyline(IPPolygonStruct *Poly,
  28.                       PolylineSegStruct *Ps, 
  29.                       RealType *StartIndex);
  30. static RealType AngularDistanceMeasure(IPVertexStruct *V,
  31.                        LsLineSegStruct *Seg);
  32. static IPVertexStruct *PolylineLastSeg(IPPolygonStruct *Poly);
  33. static RealType DistPsPs(PolylineSegStruct *Ps1,
  34.              PolylineSegStruct *Ps2,
  35.              IPPolygonStruct *Poly,
  36.              RealType StartIndex);
  37.  
  38. /*****************************************************************************
  39. * DESCRIPTION:                                                               M
  40. * Creates the appropriate data structures and invokes a plane sweep to find  M
  41. * all intersection points in scene. Intersection points that are found valid M
  42. * (see below) are treated as follows:                         M
  43. * 1. The polyline that is closer to the viewer is not modified.             M
  44. * 2. The polyline that is far from the viewer is split at the intersection   M
  45. *    location and GlblTrimIntersect amount from both sides of intersection   M
  46. *    is trimmed away as well.                             M
  47. *                                         M
  48. *   An intersection is considered valid if the following holds:             M
  49. * The intersection did not occur between two polylines with the same         M
  50. * Z value, considered with respect to GlblInterSameZ tolerance.                  M
  51. *                                         M
  52. *   The scene is assumed to be in view space, that is -1 to 1 in X, Y & Z.   M
  53. *   This assumption is used maily so set the GlblInterSameZ tolerances to    M
  54. * reasonable values.                                 M
  55. *   Polys are modified in palce and their PAux is exploited.             M
  56. *                                                                            *
  57. * PARAMETERS:                                                                M
  58. *   PObjects:     Process poly objects in this list and intersect all their  M
  59. *          edges.                             M
  60. *                                                                            *
  61. * RETURN VALUE:                                                              M
  62. *   void                                                                     M
  63. *                                                                            *
  64. * KEYWORDS:                                                                  M
  65. *   ProcessIntersections                                                     M
  66. *****************************************************************************/
  67. void ProcessIntersections(IPObjectStruct *PObjects)
  68. {
  69.     IPObjectStruct *PObj;
  70.     int PolyID = 0;
  71.     LsLineSegStruct *Ln,
  72.         *LnList = NULL;
  73.  
  74.     /* Convert the data to the format used by the plane sweep. */
  75.     for (PObj = PObjects; PObj != NULL; PObj = PObj -> Pnext) {
  76.     IPPolygonStruct *PPoly;
  77.  
  78.     if (!IP_IS_POLY_OBJ(PObj))
  79.         continue;
  80.  
  81.     if (IP_IS_POLYGON_OBJ(PObj)) {
  82.         IPPolygonStruct *Polygons, *Polygon;
  83.  
  84.         /* Convert to polylines (lines actually since every polyline has */
  85.         /* only one segment). Allow only lines for which second point    */
  86.         /* Z value is larger than first.                     */
  87.         Polygons = PObj -> U.Pl;
  88.         IP_SET_POLYLINE_OBJ(PObj);
  89.         PObj -> U.Pl = NULL;
  90.         for (Polygon = Polygons;
  91.          Polygon != NULL;
  92.          Polygon = Polygon -> Pnext) {
  93.         IPVertexStruct *V, *VTmp1, *VTmp2;
  94.  
  95.         for (V = Polygon -> PVertex;
  96.              V != NULL && V -> Pnext != NULL;
  97.              V = V -> Pnext) {
  98.             if (!IP_IS_INTERNAL_VRTX(V) &&
  99.             V -> Coord[2] <= V -> Pnext -> Coord[2]) {
  100.             VTmp2 = IPAllocVertex(0, 0, NULL, NULL);
  101.             VTmp1 = IPAllocVertex(0, 0, NULL, VTmp2);
  102.  
  103.             PT_COPY(VTmp1 -> Coord, V -> Pnext -> Coord);
  104.             PT_COPY(VTmp2 -> Coord, V -> Coord);
  105.             PObj -> U.Pl = IPAllocPolygon(0, 0, VTmp1, PObj -> U.Pl);
  106.             }
  107.         }
  108.  
  109.         /* Add the last edge. */
  110.         if (!IP_IS_INTERNAL_VRTX(V) &&
  111.             V -> Coord[2] <= Polygon -> PVertex -> Coord[2]) {
  112.             VTmp2 = IPAllocVertex(0, 0, NULL, NULL);
  113.             VTmp1 = IPAllocVertex(0, 0, NULL, VTmp2);
  114.  
  115.             PT_COPY(VTmp1 -> Coord, Polygon -> PVertex -> Coord);
  116.             PT_COPY(VTmp2 -> Coord, V -> Coord);
  117.             PObj -> U.Pl = IPAllocPolygon(0, 0, VTmp1, PObj -> U.Pl);
  118.         }
  119.         }
  120.     }
  121.  
  122.     if (!IP_IS_POLYLINE_OBJ(PObj))
  123.         continue;
  124.  
  125.     for (PPoly = PObj -> U.Pl; PPoly != NULL; PPoly = PPoly -> Pnext) {
  126.         IPVertexStruct *V;
  127.         int i = 0;
  128.  
  129.         PPoly -> PAux = NULL; /* Will use it later - make sure its NULL. */
  130.  
  131.         for (V = PPoly -> PVertex, PolyID++;
  132.          V != NULL && V -> Pnext != NULL;
  133.          V = V -> Pnext) {
  134.         PolylineSegStruct
  135.             *Ps = (PolylineSegStruct *)
  136.             IritMalloc(sizeof(PolylineSegStruct));
  137.  
  138.         Ln = (LsLineSegStruct *) IritMalloc(sizeof(LsLineSegStruct));
  139.         PT_COPY(Ln -> Pts[0], V -> Coord);
  140.         PT_COPY(Ln -> Pts[1], V -> Pnext -> Coord);
  141.         Ln -> Id = PolyID;
  142.         Ln -> Inters = NULL;         /* No intersections so far. */
  143.         Ln -> Pnext = LnList;
  144.         Ps -> Poly = PPoly;
  145.         Ps -> Index = i++;
  146.         Ln -> PAux = Ps;/* A backpointer to original polyline/index. */
  147.         LnList = Ln;
  148.         }
  149.     }
  150.     }
  151.  
  152.     LineSweep(&LnList);
  153.  
  154.     /* Eliminate invalid intersections. */
  155.     for (Ln = LnList; Ln != NULL; Ln = Ln -> Pnext) {
  156.     LsIntersectStruct *PrevInter, *Inter;
  157.  
  158.     for (Inter = Ln -> Inters, PrevInter = NULL; Inter != NULL;) {
  159.         RealType
  160.         Z1 = Ln -> Pts[0][2] * (1.0 - Inter -> t) +
  161.              Ln -> Pts[1][2] * Inter -> t,
  162.         Z2 = Inter -> OtherSeg -> Pts[0][2] * (1.0 - Inter -> OtherT) +
  163.              Inter -> OtherSeg -> Pts[1][2] * Inter -> OtherT;
  164.  
  165.         if (Z2 - Z1 < GlblInterSameZ) {
  166.         /* Eliminate this intersection - it is invalid. */
  167.         if (PrevInter) {
  168.             PrevInter -> Pnext = Inter -> Pnext;
  169.             IritFree((VoidPtr) Inter);
  170.             Inter = PrevInter -> Pnext;
  171.         }
  172.         else {
  173.             LsIntersectStruct
  174.             *TempInter = Inter -> Pnext;
  175.  
  176.             IritFree((VoidPtr) Inter);
  177.             Inter = Ln -> Inters = TempInter;
  178.         }
  179.         }
  180.         else {
  181.         PrevInter = Inter;
  182.         Inter = Inter -> Pnext;
  183.         }
  184.     }
  185.     }
  186.  
  187.     /* Split the polylines at the valid intersections and trim the ends      */
  188.     /* GlblTrimIntersect amount from both sides.                 */
  189.     /*   We first scan the entire data set and update each polyline with its */
  190.     /* set of intersection locations (saved in Polyline PAux pointer).       */
  191.     for (Ln = LnList; Ln != NULL; Ln = Ln -> Pnext) {
  192.     LsIntersectStruct
  193.         *Inter = Ln -> Inters;
  194.  
  195.     for (Inter = Ln -> Inters; Inter != NULL; Inter = Inter -> Pnext) {
  196.         PolylineSegStruct
  197.         *Ps = (PolylineSegStruct *) Ln -> PAux,
  198.         *NewPs = (PolylineSegStruct *)
  199.             IritMalloc(sizeof(PolylineSegStruct));
  200.         IPPolygonStruct
  201.         *Poly = Ps -> Poly;
  202.  
  203.         GEN_COPY(NewPs, Ps, sizeof(PolylineSegStruct));
  204.         NewPs -> t = Inter -> t;
  205.         NewPs -> Inter = Inter;
  206.         NewPs -> Pnext = NULL;
  207.  
  208.         if (Poly -> PAux) {
  209.         PolylineSegStruct *StepPs, *PrevPs,
  210.             *HeadPs = (PolylineSegStruct *) Poly -> PAux;
  211.  
  212.         /* Put this new intersection point in the right order. */
  213.         if (NewPs -> Index + NewPs -> t <
  214.             HeadPs -> Index + HeadPs -> t) {
  215.             /* Put it as first one. */
  216.             Poly -> PAux = NewPs;
  217.             NewPs -> Pnext = HeadPs;
  218.         }
  219.         else {
  220.             for (StepPs = HeadPs -> Pnext, PrevPs = HeadPs;
  221.              StepPs != NULL;
  222.              PrevPs = StepPs, StepPs = StepPs -> Pnext) {
  223.             if (NewPs -> Index + NewPs -> t <
  224.                 StepPs -> Index + StepPs -> t) {
  225.                 PrevPs -> Pnext = NewPs;
  226.                 NewPs -> Pnext = StepPs;
  227.                 break;
  228.             }
  229.             }
  230.             if (StepPs == NULL)
  231.             PrevPs -> Pnext = NewPs;
  232.         }
  233.         }
  234.         else
  235.         Poly -> PAux = NewPs;
  236.     }
  237.     }
  238.  
  239.     /* The second stage - split each polyline at each intersection point. */
  240.     for (PObj = PObjects; PObj != NULL; PObj = PObj -> Pnext) {
  241.     IPPolygonStruct *PPoly, *NewPoly;
  242.  
  243.     if (!IP_IS_POLY_OBJ(PObj) || !IP_IS_POLYLINE_OBJ(PObj))
  244.         continue;
  245.  
  246.     for (PPoly = PObj -> U.Pl; PPoly != NULL; PPoly = PPoly -> Pnext) {
  247.         PolylineSegStruct
  248.         *HeadPs = (PolylineSegStruct *) PPoly -> PAux;
  249.         IPPolygonStruct
  250.         *PStart = PPoly,
  251.         *Pnext = PPoly -> Pnext;
  252.         RealType
  253.         StartIndex = 0.0;
  254.  
  255.         while (HeadPs != NULL) {
  256.         PolylineSegStruct
  257.             *NextPs = HeadPs -> Pnext;
  258.  
  259.         if ((NewPoly = SplitPolyline(PPoly, HeadPs, &StartIndex))
  260.                                      != NULL) {
  261.             NewPoly -> Pnext = PPoly -> Pnext;
  262.             PPoly -> Pnext = NewPoly;
  263.             PPoly = NewPoly;
  264.         }
  265.  
  266.         IritFree((VoidPtr) HeadPs);
  267.         HeadPs = NextPs;
  268.         }
  269.         if (PStart -> Pnext != Pnext) {
  270.         IPPolygonStruct  *PTmp;
  271.  
  272.         /* Polyline was split. Add attributes to signal that. */
  273.         AttrSetIntAttrib(&PStart -> Attrs, "widenend", WIDEN_END_END);
  274.         for (PTmp = PStart -> Pnext;
  275.              PTmp != Pnext;
  276.              PTmp = PTmp -> Pnext) {
  277.             AttrSetIntAttrib(&PTmp -> Attrs, "widenend",
  278.                      WIDEN_END_START |
  279.                          (PTmp -> Pnext == Pnext ?
  280.                       0 : WIDEN_END_END) );
  281.         }
  282.         }
  283.     }
  284.     }
  285.  
  286. #ifdef DEBUG_DUMP_INTERS
  287. #define CROSS_SIZE 0.02    
  288.     fprintf(stderr,
  289.         "gsave\n0 setlinewidth\n72 72 scale\n4 5.5 translate\n3 3 scale\n\n");
  290.  
  291.     for (Ln = LnList; Ln != NULL; Ln = Ln -> Pnext) {
  292.     LsIntersectStruct *Inter;
  293.  
  294.     for (Inter = Ln -> Inters; Inter != NULL; Inter = Inter -> Pnext) {
  295.         RealType
  296.         x = Ln -> Pts[0][0] + Inter -> t * Ln -> _Vec[0],
  297.         y = Ln -> Pts[0][1] + Inter -> t * Ln -> _Vec[1];
  298.  
  299.         fprintf(stderr, "255 0 0 setrgbcolor\n");
  300.         fprintf(stderr, "newpath %lf %lf moveto %lf %lf lineto stroke\n",
  301.            x - CROSS_SIZE, y, x + CROSS_SIZE, y);
  302.         fprintf(stderr, "newpath %lf %lf moveto %lf %lf lineto stroke\n",
  303.            x, y - CROSS_SIZE, x, y + CROSS_SIZE);
  304.         fprintf(stderr, "0 0 0 setrgbcolor\n");
  305.     }
  306.     }
  307. #endif /* DEBUG_DUMP_INTERS */
  308.  
  309. #ifdef DEBUG_DUMP_POLYS
  310.     fprintf(stderr, "gsave\n");
  311.  
  312. #   ifndef DEBUG_DUMP_INTERS
  313.     fprintf(stderr,
  314.         "0 setlinewidth\n72 72 scale\n4 5.5 translate\n3 3 scale\n\n");
  315. #   endif /* DEBUG_DUMP_INTERS */
  316.  
  317.     /* Convert the data to the format used by the plane sweep. */
  318.     for (PObj = PObjects; PObj != NULL; PObj = PObj -> Pnext) {
  319.     IPPolygonStruct *PPoly;
  320.  
  321.     if (!IP_IS_POLY_OBJ(PObj) || !IP_IS_POLYLINE_OBJ(PObj))
  322.         continue;
  323.  
  324.     for (PPoly = PObj -> U.Pl; PPoly != NULL; PPoly = PPoly -> Pnext) {
  325.         IPVertexStruct
  326.         *V = PPoly -> PVertex;
  327.  
  328.         if (V != NULL) {
  329.         fprintf(stderr, "newpath %lf %lf moveto\n",
  330.                V -> Coord[0], V -> Coord[1]);
  331.         for (V = V -> Pnext; V != NULL; V = V -> Pnext)
  332.             fprintf(stderr, " %lf %lf lineto\n",
  333.                V -> Coord[0], V -> Coord[1]);
  334.         fprintf(stderr, "stroke\n");
  335.         }
  336.     }
  337.     }
  338.  
  339.     fprintf(stderr, "grestore\nshowpage\n");
  340. #endif /* DEBUG_DUMP_POLYS */
  341. }
  342.  
  343. /*****************************************************************************
  344. * DESCRIPTION:                                                               *
  345. * Splits Poly into two at the specified location by Ps. Location is defined  *
  346. * by a point Index and a parameter (between zero and one) along the line     *
  347. * from point Index to point Index+1.                         *
  348. *   The split point is trimmed with extra distance as specified by the       *
  349. * GlblTrimIntersect global variable.                         *
  350. *   First point of Point is given by StartIndex which is also updated to     *
  351. * hold the new StartIndex after trimming occured.                 *
  352. *   NULL is returned if split is too close to the starting point of Poly.    *
  353. *   Note Poly may result in a polyline that is empty (i.e. no vertices).     *
  354. *                                                                            *
  355. * PARAMETERS:                                                                *
  356. *   Poly:        Poly to split into two at Ps.                               *
  357. *   Ps:          Location where to split Poly. Index of edge (vertex) in     *
  358. *         Poly and parameter between zero and one to that edge.         *
  359. *   StartIndex:  What we trimmed already. Do nothing if Ps below StartIndex. *
  360. *                                                                            *
  361. * RETURN VALUE:                                                              *
  362. *   IPPolygonStruct *:   Second half of split poly if split, NULL otherwise. *
  363. *                        First half is in Poly, modified in place.           *
  364. *****************************************************************************/
  365. static IPPolygonStruct *SplitPolyline(IPPolygonStruct *Poly,
  366.                       PolylineSegStruct *Ps, 
  367.                       RealType *StartIndex)
  368. {
  369.     int i;
  370.     RealType t, TrimmedDist, AngularMeasure;
  371.     PointType InterPt;
  372.     IPVertexStruct *NewV, *InterV,
  373.     *V = Poly -> PVertex;
  374.     IPPolygonStruct *NewPoly;
  375.  
  376.     if (Ps -> Index + Ps -> t < *StartIndex)
  377.     return NULL;
  378.  
  379.     /* Find the vertex, the intersection point is between it and the next. */
  380.     for (i = Ps -> Index - ((int) *StartIndex); i > 0 && V != NULL; i--)
  381.     V = V -> Pnext;
  382.     if (V == NULL || V -> Pnext == NULL)
  383.     IritFatalError("Vertex index is too large.\n");
  384.     InterV = V;
  385.     AngularMeasure = AngularDistanceMeasure(InterV, Ps -> Inter -> OtherSeg);
  386.  
  387.     /* Find the exact intersection location and split the polyline. */
  388.     if (((int) *StartIndex) == Ps -> Index) {
  389.     t = *StartIndex - ((int) *StartIndex);
  390.     t = (Ps -> t - t) / (1.0 - t);
  391.     }
  392.     else
  393.     t = Ps -> t;
  394.     PT_BLEND(InterPt, InterV -> Pnext -> Coord, InterV -> Coord, t);
  395.     *StartIndex = Ps -> t + Ps ->Index;
  396.  
  397.     NewV = IPAllocVertex(0, 0, NULL, InterV -> Pnext);
  398.     PT_COPY(NewV -> Coord, InterPt);
  399.     NewPoly = IPAllocPolygon(0, 0, NewV, NULL);
  400.  
  401.     NewV = IPAllocVertex(0, 0, NULL, NULL);
  402.     PT_COPY(NewV -> Coord, InterPt);
  403.     InterV -> Pnext = NewV;
  404.  
  405.     /* Trim the end of the first polyline (the original). */
  406.     TrimmedDist = GlblTrimIntersect * AngularMeasure;
  407.     while (Poly -> PVertex != NULL &&
  408.        Poly -> PVertex -> Pnext != NULL &&
  409.        TrimmedDist > 0.0) {
  410.     RealType Dist;
  411.  
  412.     V = PolylineLastSeg(Poly);
  413.     Dist = SegmentLength(V);
  414.     if (TrimmedDist > Dist) {
  415.         /* Eliminate the entire segment. */
  416.         TrimmedDist -= Dist;
  417.         V -> Pnext -> Pnext = NULL;
  418.         IPFreeVertexList(V -> Pnext);
  419.         V -> Pnext = NULL;
  420.         if (V == Poly -> PVertex) {   /* Eliminated the entire polyline. */
  421.         V -> Pnext = NULL;
  422.         IPFreeVertexList(V);
  423.         Poly -> PVertex = NULL;
  424.         }
  425.     }
  426.     else {
  427.         /* Update the last point to the right distance. */
  428.         t = TrimmedDist / Dist;
  429.         TrimmedDist = 0.0;
  430.         PT_BLEND(V -> Pnext -> Coord, V -> Coord, V -> Pnext -> Coord, t);
  431.     }
  432.     }
  433.  
  434.     /* Trim the beginning of the second polyline. */
  435.     TrimmedDist = GlblTrimIntersect * AngularMeasure;
  436.     if (Ps -> Pnext == NULL ||
  437.     DistPsPs(Ps, Ps -> Pnext, NewPoly, *StartIndex) > TrimmedDist) {
  438.     while (NewPoly -> PVertex != NULL &&
  439.            NewPoly -> PVertex -> Pnext != NULL &&
  440.            TrimmedDist > 0.0) {
  441.         RealType Dist;
  442.  
  443.         V = NewPoly -> PVertex;
  444.         Dist = SegmentLength(V);
  445.         if (TrimmedDist > Dist) {
  446.         /* Eliminate the entire segment. */
  447.         TrimmedDist -= Dist;
  448.         NewPoly -> PVertex = V -> Pnext;
  449.         V -> Pnext = NULL;
  450.         IPFreeVertexList(V);
  451.         if (V -> Pnext == NULL) { /* Eliminated the entire polyline. */
  452.             V -> Pnext = NULL;
  453.             IPFreeVertexList(V);
  454.             NewPoly -> PVertex = NULL;
  455.         }
  456.         *StartIndex = 1 + ((int) *StartIndex);
  457.         }
  458.         else {
  459.         /* Update the first point with the right distance. */
  460.         t = TrimmedDist / Dist;
  461.         TrimmedDist = 0.0;
  462.         PT_BLEND(V -> Coord, V -> Pnext -> Coord, V -> Coord, t);
  463.         *StartIndex += t * (1.0 - (*StartIndex - ((int) *StartIndex)));
  464.         }
  465.     }
  466.     }
  467.  
  468.     return NewPoly;
  469. }
  470.  
  471. /*****************************************************************************
  472. * DESCRIPTION:                                                               *
  473. * Returns one over the sine of the angle between the line segment from V     *
  474. * to V -> Pnext and the line segment specified by Seg.                 *
  475. *                                                                            *
  476. * PARAMETERS:                                                                *
  477. *   V:         Vertex to compute one of the sine of angle with Seg.          *
  478. *   Seg:       Segment to compute one of the sine of angle with V.           *
  479. *                                                                            *
  480. * RETURN VALUE:                                                              *
  481. *   RealType:  One over the sine of the angle between Vand Seg.              *
  482. *****************************************************************************/
  483. static RealType AngularDistanceMeasure(IPVertexStruct *V, LsLineSegStruct *Seg)
  484. {
  485.     RealType CosAngle, AngularMeasure;
  486.     VectorType V1, V2;
  487.  
  488.     if (!GlblAngularDistance)
  489.     return 1.0;
  490.  
  491.     PT_SUB(V1, V -> Pnext -> Coord, V -> Coord);
  492.     PT_SUB(V2, Seg -> Pts[0], Seg -> Pts[1]);
  493.     V1[2] = V2[2] = 0.0;
  494.     if (PT_LENGTH(V1) <= PT_NORMALIZE_ZERO ||
  495.     PT_LENGTH(V2) <= PT_NORMALIZE_ZERO)
  496.     return 1.0;
  497.  
  498.     PT_NORMALIZE(V1);
  499.     PT_NORMALIZE(V2);
  500.  
  501.     CosAngle = DOT_PROD(V1, V2);
  502.  
  503.     AngularMeasure = 1.0 / sqrt(1.0 + EPSILON - SQR(CosAngle));
  504.  
  505.     return MIN(AngularMeasure, 5.0);     /* Make sure it is not too far off. */
  506. }
  507.  
  508. /*****************************************************************************
  509. * DESCRIPTION:                                                               *
  510. * Returns a pointer to last line segment of polyline. The returned pointer   *
  511. * is the address of V where V -> Pnext is the last vertex in polyline.       *
  512. *                                                                            *
  513. * PARAMETERS:                                                                *
  514. *   Poly:        To find its last segment.                                   *
  515. *                                                                            *
  516. * RETURN VALUE:                                                              *
  517. *   IPVertexStruct *:   First vertex of last segment (together with its      *
  518. *                       Pnext).                                              *
  519. *****************************************************************************/
  520. static IPVertexStruct *PolylineLastSeg(IPPolygonStruct *Poly)
  521. {
  522.     IPVertexStruct
  523.     *V = Poly -> PVertex;
  524.  
  525.     if (V == NULL || V -> Pnext == NULL)
  526.     return NULL;
  527.  
  528.     while (V -> Pnext -> Pnext != NULL)
  529.     V = V -> Pnext;
  530.  
  531.     return V;
  532. }
  533.  
  534. /*****************************************************************************
  535. * DESCRIPTION:                                                               M
  536. * Computes the XY length of the line segment from V to V -> Pnext vertices.  M
  537. *                                                                            *
  538. * PARAMETERS:                                                                M
  539. *   V:         First vertex of edge (together with its Pnext).            M
  540. *                                                                            *
  541. * RETURN VALUE:                                                              M
  542. *   RealType:  Length of edge.                             M
  543. *                                                                            *
  544. * KEYWORDS:                                                                  M
  545. *   SegmentLength                                                            M
  546. *****************************************************************************/
  547. RealType SegmentLength(IPVertexStruct *V)
  548. {
  549.     return DIST_PT_PT_2D(V -> Coord, V -> Pnext -> Coord);
  550. }
  551.  
  552. /*****************************************************************************
  553. * DESCRIPTION:                                                               *
  554. * Computes the XY length along Poly from Ps1 to Ps2                 *
  555. *                                                                            *
  556. * PARAMETERS:                                                                *
  557. *   Ps1, Ps2:     Locations on Poly (index of edge + parameter along edge)   *
  558. *   Poly:         For which distance along of two points is to be computed.  *
  559. *   StartIndex:   Index in Ps1/2 is relative to this.                        *
  560. *                                                                            *
  561. * RETURN VALUE:                                                              *
  562. *   RealType:     XY distance.                                               *
  563. *****************************************************************************/
  564. static RealType DistPsPs(PolylineSegStruct *Ps1,
  565.              PolylineSegStruct *Ps2,
  566.              IPPolygonStruct *Poly,
  567.              RealType StartIndex)
  568. {
  569.     int i;
  570.     RealType Dist;
  571.     PointType Pt;
  572.     IPVertexStruct
  573.     *V = Poly -> PVertex;
  574.  
  575.     /* Find length of segment of first Ps. */
  576.     for (i = Ps1 -> Index - ((int) StartIndex);
  577.      i > 0 && V != NULL && V -> Pnext != NULL;
  578.      i--)
  579.     V = V -> Pnext;
  580.     PT_BLEND(Pt, V -> Pnext -> Coord, V -> Coord, Ps1 -> t);
  581.     Dist = DIST_PT_PT_2D(Pt, V -> Pnext -> Coord);
  582.  
  583.     /* Accumulates the full line segments in between. */
  584.     for (i = Ps2 -> Index - Ps1 -> Index, V = V -> Pnext;
  585.      i > 1 && V != NULL && V -> Pnext != NULL;
  586.      i++, V = V -> Pnext) {
  587.     Dist += SegmentLength(V);
  588.     }
  589.  
  590.     /* Add the Ps2 partial length. */
  591.     if (Ps1 -> Index != Ps2 -> Index && V != NULL && V -> Pnext != NULL) {
  592.     PT_BLEND(Pt, V -> Pnext -> Coord, V -> Coord, Ps2 -> t);
  593.     Dist += DIST_PT_PT_2D(Pt, V -> Coord);
  594.     }
  595.  
  596.     return Dist;
  597. }
  598.